#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

template <typename T>
class MyVector {
 private:
  T *_data;
  size_t _size;
  size_t _capacity;
  void check_range(size_t index) {
    if (index >= _size) {
      stringstream ss;
      ss << "out of range, index: " << index << ", size = " << _size;
      throw out_of_range(ss.str());
    }
  }

 public:
  class iterator {
   private:
    T *ptr;

   public:
    using value_type = T;
    using iterator_category = random_access_iterator_tag;
    using difference_type = ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    iterator() {}
    iterator(T *ptr) : ptr(ptr) {}
    T &operator*() const { return *ptr; }
    T *operator->() const { return ptr; }
    iterator &operator++() {
      ptr++;
      return *this;
    }
    iterator operator++(int) {
      iterator temp = *this;
      ptr++;
      return temp;
    }
    iterator &operator--() {
      ptr--;
      return *this;
    }
    iterator operator--(int) {
      iterator temp = *this;
      ptr--;
      return temp;
    }
    iterator operator+(int n) const { return iterator(ptr + n); }
    iterator operator-(int n) const { return iterator(ptr - n); }
    int operator-(const iterator &other) const { return ptr - other.ptr; }
    bool operator<(const iterator &other) const { return ptr < other.ptr; }
    bool operator==(const iterator &other) const { return ptr == other.ptr; }
    bool operator!=(const iterator &other) const { return ptr != other.ptr; }
  };
  MyVector() : _data(nullptr), _size(0), _capacity(0) {}
  MyVector(size_t n, const T &init = T())
      : _data(new T[n]), _size(n), _capacity(n) {
    for (size_t i = 0; i < n; i++) _data[i] = init;
  }
  MyVector(const MyVector<T> &other)
      : _data(new T[other.size()]),
        _size(other.size()),
        _capacity(other.size()) {
    for (size_t i = 0; i < other.size(); i++) _data[i] = other[i];
  }
  MyVector(const initializer_list<T> &init)
      : _data(new T[init.size()]), _size(0), _capacity(init.size()) {
    for (T x : init) _data[_size++] = x;
  }
  ~MyVector() { delete[] _data; }
  T &operator[](size_t index) { return _data[index]; }
  const T &operator[](size_t index) const { return _data[index]; }
  T &at(size_t index) {
    check_range(index);
    return _data[index];
  }
  const T &at(size_t index) const {
    check_range(index);
    return _data[index];
  }
  size_t size() const { return _size; }
  size_t capacity() const { return _capacity; }
  void reserve(size_t new_capacity) {
    if (new_capacity > _capacity) {
      _capacity = new_capacity;
      T *new_data = new T[_capacity];
      for (size_t i = 0; i < _size; i++) new_data[i] = _data[i];
      delete[] _data;
      _data = new_data;
    }
  }
  void push_back(const T &elem) {
    if (_size == _capacity) reserve(_capacity == 0 ? 1 : _capacity * 2);
    _data[_size++] = elem;
  }
  void resize(size_t new_size, const T &init = T()) {
    if (new_size > _capacity) reserve(new_size);
    for (size_t i = _size; i < new_size; i++) _data[i] = init;
    _size = new_size;
  }
  void pop_back() {
    if (_size == 0) throw out_of_range("can not pop_back empty vector");
    _size --;
  }
  void clear() { _size = 0; }
  iterator begin() const { return iterator(_data); }
  iterator end() const { return iterator(_data + _size); }

  void insert(const iterator &pos, T x) {
    size_t index = pos - begin();
    if (_size == _capacity) reserve(_capacity == 0 ? 1 : _capacity * 2);
    for (size_t i = _size; i > index; i --) _data[i] = _data[i - 1];
    _data[index] = x;
    _size ++;
  }
  void erase(const iterator &pos) {
    for (size_t i = pos - begin(); i < _size - 1; i ++) {
      _data[i] = _data[i + 1];
    }
    _size --;
  }
  void erase(const iterator &start, const iterator &end) {
    int diff = end - start;
    for (size_t i = start - begin(); i < _size - diff; i ++) {
      _data[i] = _data[i + diff];
    }
    _size -= diff;
  }

  MyVector<T>& operator=(const MyVector<T> &other) {
    if (this != &other) {
      delete[] _data;
      _data = new T[other.size()];
      _size = other.size();
      _capacity = other.capacity();
      for (size_t i = 0; i < _size; i ++) _data[i] = other[i];
    }
    return *this;
  }
  T &front() { return _data[0]; }
  const T&front() const { return _data[0]; }
  T &back() { return _data[_size - 1]; }
  const T&back() const { return _data[_size - 1]; }
  bool empty() const { return _size == 0; }

  template<typename... Args>
  void emplace_back(const Args&... args) {
    if (_size == _capacity) reserve(_capacity == 0 ? 1 : _capacity * 2);
    _data[_size++] = T(args...);
  }
};

int main() {
}
